package laity.linkedList;

import java.util.Stack;

/**
 * @author: Laity
 * @Project: JavaLaity
 * @Package: laity.linkedList.SingleLinkedListDemo
 * @Date: 2022年09月19日 16:38
 * @Description: 单链表
 * <p>
 * 特点：链式存储 - 链表的各个节点不一定是连续存储的
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // 进行测试
        // 先创建节点
        HeroNode heroNode1 = new HeroNode(1, "松江", "及时雨");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode2 = new HeroNode(2, "吕俊毅", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");

        // 创建一个链表
        SingleLinkedList linkedList = new SingleLinkedList();
        // 加入
        linkedList.addByOrder(heroNode1);
        linkedList.addByOrder(heroNode4);
        linkedList.addByOrder(heroNode3);
        linkedList.addByOrder(heroNode3);
        linkedList.addByOrder(heroNode2);
        linkedList.addByOrder(heroNode4);
        // 显示一把
        linkedList.list();
        System.out.println("===============修改后的链表情况===============");
        // 修改
        HeroNode heroNode5 = new HeroNode(2, "张强", "玉麒麟");
        linkedList.update(heroNode5);
        // 显示一把
        linkedList.list();

        // 删除一个节点
//        linkedList.del(1);
//        linkedList.del(2);
//        linkedList.del(3);
        linkedList.del(4);
        // 删除后再显示
        System.out.println("===============删除后的链表情况===============");
        linkedList.list();

        // 测试：获取到单链表的节点个数
        System.out.println("单链表的节点个数:" + getLength(linkedList.getHead()));

        // 测试：新浪面试题
        HeroNode res = findLastIndexNode(linkedList.getHead(), 1);
        System.out.println("新浪面试题:" + res);

        // 测试：百度面试题
        System.out.println("===============百度面试题===============");
        reversePrint(linkedList.getHead());

        // 测试：腾讯面试题 - 单链表进行反转
        System.out.println("===============反转后的链表情况===============");
        reverseList(linkedList.getHead());
        linkedList.list();

    }

    // TODO: 百度面试题
    public static HeroNode multiply(HeroNode head) {
        if (head.next == null) {
            return null;
        }
        System.out.println(head.next);
        return multiply(head.next);
    }

    // TODO：逆序打印
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return;
        }
        // 创建一个栈，将各个节点压栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        // 将链表的所有节点压入栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    // TODO: 腾讯面试题 - 将单链表反转
    public static void reverseList(HeroNode head) {
        // 判断是否为空和节点个数 - 如果为空或者节点个数只有一个的情况下 直接返回不需要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        // 定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");
        while (cur != null) {
            next = cur.next; // 暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next; // 将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;  // 将 cur 连接到新的链表上
            cur = next; // 让cur后移
        }
        // 将 head.next 指向reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }


    // TODO: 方法：获取到单链表的节点个数（如果带头节点的链表，需要不统计头节点）

    /**
     * @param head 链表的头节点
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            // 空链表
            return 0;
        }
        int length = 0;
        // 定义一个辅助变量,这里我们没有统计头节点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next; // 遍历
        }
        return length;
    }

    // TODO:新浪面试题 - 查询单链表中倒数第K个节点
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        // 判断是否为空
        if (head.next == null) {
            return null; // 链表为空，没有找到
        }
        int size = getLength(head); // 链表的有效节点长度
        if (index <= 0 || index > size) {
            return null;  // index 不在范围
        }
        // 定义一个辅助变量
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }
}


// 定义SingleLinkedList管理我们的英雄
class SingleLinkedList {
    // 初始化一个头节点，头节点先不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 当不考虑编号的顺序时，找到当前链表的最后节点，将最后这个节点的next 指向 新的节点
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，因此我们需要一个辅助变量 temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后,就将temp后移
            temp = temp.next;
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    // TODO:第二种添加英雄的方式
    public void addByOrder(HeroNode heroNode) {
        // 因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        // 因为单链表，因此我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false; // 标识添加的编号是否存在，默认为false;
        while (true) {
            if (temp.next == null) {
                // 说明到链表的最后
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 位置找到了，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {
                // 说明希望添加的heroNode的编号依然存在
                flag = true; // 说明编号存在
                break;
            }
            temp = temp.next; // 后移，遍历当前的链表
        }
        // 判断flag的值
        if (flag) {
            System.out.printf("准备插入的英雄编号 %d 已经存在，不能添加\n", heroNode.no);
        } else {
            // 插入到链表中，temp 的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // TODO:修改节点的信息，根据编号来修改，即no编号不能修改
    public void update(HeroNode newHeroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        // 找到需要修改的节点，根据no编号
        // 定义一个辅助节点
        HeroNode temp = head.next;
        boolean flag = false; // 表示是否找到该节点
        while (true) {
            if (temp == null) {
                break; // 表示链表已经遍历结束了
            }
            if (temp.no == newHeroNode.no) {
                // 找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else { // 没有找到节点
            System.out.printf("没有找到要修改的编号 %d 节点\n", newHeroNode.no);
        }
    }

    // TODO:删除节点
    // 思路: head不能动，因此我们需要一个辅助temp节点来帮我们找到 待删除节点的前一个节点
    // 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false; // 标识是否找到待删除的节点
        while (true) {
            if (temp.next == null) {
                // 说明找到了最后
                break;
            }
            if (temp.next.no == no) {
                // 找到了待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 判断flag
        if (flag) {
            // 说明找到可以删除
            temp.next = temp.next.next;
        } else {
            // 没有找到
            System.out.printf("要删除的 d% 节点不存在\n", no);
        }
    }

    //

    // 显示链表【遍历】
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        // 因为头节点不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //  判断是否到链表最后
            if (temp == null) {
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 将next后移,一定小心
            temp = temp.next;
        }
    }
}

// 定义一个HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no; // 英雄的编号
    public String name; // 英雄的名字
    public String nickname; // 英雄的昵称
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int hNo, String name, String nickname) {
        this.no = hNo;
        this.name = name;
        this.nickname = nickname;
    }

    // 为了显示方便，我们重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
